//
// Created by edward on 23-2-13.
//

#ifndef CONCURRENCE_LOCKFREEQUEUE_H
#define CONCURRENCE_LOCKFREEQUEUE_H

#include "utils.h"
#include <memory>
#include <thread>

namespace edward::multithread {

    template<typename T>
    class LockFreeQueue {
        using Ptr = std::shared_ptr<T>;
        struct Node;
        using NodePtr = std::shared_ptr<Node>;
//        using NodePtr = Node*;
        static Ptr tmpP;
    public:
        LockFreeQueue(): head_(std::make_shared<Node>()), tail_(head_.load()) {}
        ~LockFreeQueue() {
            /*
            //把尚存在队列的节点删除
            NodePtr node = head_.load(), p;
            while (node) {
                p = node->next_;
                delete node;
                node = p;
            }
             */
        }

        void push(T t) {
//            NodePtr newTail = std::make_shared<Node>();
            Ptr data = std::make_shared<T>(std::move(t));
            NodePtr newTail = std::make_shared<Node>();
            NodePtr oldTail = tail_.load();
            Ptr oldData = nullptr;
            while (!oldTail->data_.compare_exchange_weak(oldData, data)) {
                oldTail = tail_.load();
                oldData.reset();
            }

            oldTail->next_ = newTail;
            tail_.store(newTail);
        }

        Ptr tryPop() {
            NodePtr oldHead = head_.load();
            if (oldHead == tail_.load()) return Ptr{};  //空队列

            while (!head_.compare_exchange_weak(oldHead, oldHead->next_)) {
                if (oldHead == tail_.load()) return Ptr{};  //空队列
            }
            Ptr ret = oldHead->data_.load();
            oldHead->data_ = tmpP;

//            delete oldHead; //已经没有人可以看到了

            return ret;
        }

        Ptr pop() {
            Ptr ret;
            while (!(ret = tryPop())) { //自旋
                std::this_thread::yield();
            }
            return ret;
        }

        bool empty() const {
            return head_.load() == tail_.load();
        }

    private:
        struct Node {
            std::atomic<Ptr> data_;
            NodePtr next_;
            Node() {
//                edward::print("ctor");
            }
            explicit Node(Ptr data, NodePtr next = NodePtr{}): data_(data), next_(next) {
//                edward::print("ctor");
            }
            ~Node() {
//                edward::print("dtor");
            }
        };
        std::atomic<NodePtr> head_, tail_;
    };

    template<typename T>
    LockFreeQueue<T>::Ptr LockFreeQueue<T>::tmpP = std::make_shared<T>();
}


#endif //CONCURRENCE_LOCKFREEQUEUE_H
